<html>
  <head></head>
  <body>
    <p>排序</p>

    <script>
      // 冒泡排序
      // 时间复杂度 O(n²)  空间复杂度O(1)
      function bubbleSort(arr) {
        for (let i = 0; i < arr.length; i++) {
          for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
              const temp = arr[j]
              arr[j] = arr[j + 1]
              arr[j + 1] = temp
            }
          }
        }
        return arr
      }

      // 选择排序
      // 时间复杂度 O(n²)  空间复杂度O(1)
      function selectionSort(arr) {
        for (let i = 0; i < arr.length - 1; i++) {
          let minIndex = i
          for (let j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) minIndex = j
          }
          const temp = arr[i]
          arr[i] = arr[minIndex]
          arr[minIndex] = temp
        }
        return arr
      }

      // 快速排序
      // 时间复杂度 O(nlogn)：递归循环次数复杂度O(logn)【假设递归x次，数组被分治为n份，2^x = n,则 n = logn】；每一次递归循环时间复杂度,filter遍历,O(n)
      // 空间复杂度O(nlogn)：递归循环次数复杂度O(logn)【假设递归x次，数组被分治为n份，2^x = n,则 n = logn】；每一次递归循环空间复杂度,生成一个新的数组,O(n)
      function quickSort(arr) {
        if (arr.length <= 1) return arr
        const base = arr[0]
        const left = quickSort(arr.slice(1).filter(item => item <= base))
        const right = quickSort(arr.slice(1).filter(item => item > base))
        return [...left, base, ...right]
      }

      const arr_1 = [55, 32, 78, 99, 12, 64, 90]
      const arr_2 = [55, 32, 78, 99, 12, 64, 90]
      const arr_3 = [55, 32, 78, 99, 32, 12, 64, 90, 0, 99, 99]
      console.log('冒泡排序', bubbleSort(arr_1))
      console.log('选择排序', selectionSort(arr_2))
      console.log('快速排序', quickSort(arr_3))
    </script>
  </body>
</html>
